import java.util.*;

public class Text {
    //692. 前K个高频单词
//    给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//    返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    public List<String> topKFrequent(String[] words, int k) {
        //1. 创建HashMap 遍历 words 统计次数
        HashMap<String,Integer> map = new HashMap<>();
        for(String word: words) {
            if(map.get(word) == null) {
                // 不存在map当中，直接插入
                map.put(word,1);
            }else {
                // 已经存在map当中
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //当前已经将words遍历 并存储统计到map当中了
        //2. 接下来创建小根堆，将前k个 频率的单词放入到小根堆当中
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0 ) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 遍历map
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                // 堆的个数小于k
                minHeap.offer(entry);
            }else {
                // 堆的个数大于堆，就跟对顶元素对比，比对顶元素大就进去
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    // 当前的entry 比 堆顶元素top 大
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for(int i = 0;i < k;i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
